Schick's Problem on RE sets
April-30-10
8:27 PM
Itai's Solution:
Question: For a subset B of N (the naturals), write B={b_1<b_2<b_3<...} and let
TB={k+b_k}. If B is RE, is it always true that TB is RE?
Answer: No. Let A be the set of n's such that Turing machine number n halts,
and let B={2^n: n\in A}. Then B is clearly RE, but TB is not. Indeed, elements
of TB are of the form 2^n+k, where 0<=k<=n, so k is much smaller than 2^n. Thus
if you get an element of TB you can immediately find its n and k. But k is the
number of machines before n that stop. If you know that number it is easy to
find out which are the machines that stop - you simply run all n machines in
parallel until exactly k of them stop, and you now know that the rest will
never stop. So if you have a machine that can produce arbitrarily large
elements of TB then you can solve the halting problem; so TB is not RE.